package main

import (
	"container/list"
)

func numSquares2(n int) int {
	queue := list.New()
	queue.PushBack(n)
	nums := make([]int, 0)

	getAllNums := func(n int) {
		for i := 1; i < n; i++ {
			if i*i > n {
				break
			}
			nums = append(nums, i*i)
		}
	}
	mark := make([]bool, n+1)

	getAllNums(n)

	layer := 1
	for queue.Len() > 0 {
		size := queue.Len()
		for i := 0; i < size; i++ {
			front := queue.Front().Value.(int)
			for k := 0; k < len(nums); k++ {
				next := front - nums[k]
				if next == 0 {
					return layer
				}

				if next < 0 {
					continue
				}
				if mark[next] {
					continue
				}
				queue.PushBack(next)
				mark[next] = true
			}

			queue.Remove(queue.Front())
		}

		layer++
	}

	return layer
}

func numSquares(n int) int {
	dp := make([]int, n+1)

	min := func(a, b int) int {
		if a > b {
			return b
		}
		return a
	}

	for i := 1; i <= n; i++ {
		dp[i] = i
		for j := i; i-j*j >= 0; j++ {
			dp[i] = min(dp[i], dp[i-j*j]+1)
		}
	}

	return dp[len(dp)-1]

}
func main() {
	numSquares(12)
}
